Не так далеко, как я мог найти. Для тех, кто хочет сделать это в будущем:
я использовал tkSimpleDialog и ttkcalendar.py (с изменениями из этого SO сообщения) сделать CalendarDialog . Модифицированные версии трех файлов доступны на моем github .
Ниже приведен код в моем CalendarDialog.py :
import Tkinter
import ttkcalendar
import tkSimpleDialog
class CalendarDialog(tkSimpleDialog.Dialog):
"""Dialog box that displays a calendar and returns the selected date"""
def body(self, master):
self.calendar = ttkcalendar.Calendar(master)
self.calendar.pack()
def apply(self):
self.result = self.calendar.selection
# Demo code:
def main():
root = Tkinter.Tk()
root.wm_title("CalendarDialog Demo")
def onclick():
cd = CalendarDialog(root)
print cd.result
button = Tkinter.Button(root, text="Click me to see a calendar!", command=onclick)
button.pack()
root.update()
root.mainloop()
if __name__ == "__main__":
main()
У вас есть проблема удовлетворения ограничений ; их отношение к NP интересно, потому что они, как правило, NP, но часто не являются NP-полными, т.е. они поддаются полиномиальным решениям.
Как ebo отметило в комментариях, ваша ситуация звучит так, как будто ее можно сформулировать как задача точного покрытия , к которой вы можете применить алгоритм Кнута X . Если вы выберете этот прием, сообщите нам, как он вам подходит.
Похоже, у вас есть проблема удовлетворения ограничений .
В вашем случае я бы в первую очередь рассмотрел методы распространения ограничений - вы можете уменьшить проблему до управляемого размера, который путь.
Что произойдет, если никто не соответствует критериям?
То, что вы описываете, является «проблемой соседа по комнате», она легко описана в этом тезисе .
Потерпите меня, я ищу лучшие ссылки.
РЕДАКТИРОВАТЬ
Вот еще один довольно плотный тезис .
Я не уверен, что ваша проблема - NP, от этого не пахнет, но что бы я сделал на вашем месте, так это упорядочил бы требования к позициям, чтобы вы пытались заполнить наиболее конкретный первый, поскольку на эти должности будет доступно меньше людей, поэтому вам с меньшей вероятностью придется много отказываться. Нет причин, по которым вы не должны комбинировать это с алгоритмом X, алгоритмом чистого Кнута.
Что касается меня, я, скорее всего, попытался бы найти сокращение до проблемы сопоставления двудольных графов . Кроме того, доказать, что проблема является NP, обычно намного сложнее, чем оставаться, вы не можете найти полиномиальное решение.
Мне кажется, у вас есть пара отдельных проблем, которые было бы намного проще решить:
- выберите одного врача из команды A - выбрать другого врача из любой команды - выберите двух медсестер
Итак, у вас есть три независимые проблемы.
Пояснение: нужно ли вам иметь двух врачей (одного из указанной команды) и двух медсестер, или одного врача из указанной команды, двух медсестер , и еще один, который может быть врачом или медсестрой?
Некоторые вопросы:
Если вы хотите удовлетворить ограничения точно , то я бы упорядочил ограничения по строгости, то есть те, которые труднее всего достичь (например, доктор И команда A в приведенном выше примере) должны быть сначала проверены !
Если вы хотите удовлетворить ограничения приблизительно , тогда его другая история ... вам нужно будет указать какую-то функцию взвешивания / важности, которая определяет, что мы хотели бы иметь, когда мы можем '
Я оставлю теорию другим, так как моя математическая смекалка не так уж велика, но вы можете найти такой инструмент, как Cassowary / Cassowary.net или NSolver, полезным для декларативного представления вашей проблемы в виде проблема удовлетворения ограничений, а затем решить ограничения.
В таких инструментах симплекс-метод в сочетании с распространением ограничений часто используется для детерминированного сокращения пространства решений и последующего поиска оптимального решения с учетом функции стоимости. Для больших пространств решений (которые, кажется, неприменимы к размеру проблемы, которую вы указываете), иногда используются генетические алгоритмы.
Если я правильно помню, NSolver также включает в пример кода упрощение реальной задачи включения медсестер. над которым доктор Чун работал в Гонконге. И есть документ о проделанной им работе.