Возможная полная NP проблема?

Не так далеко, как я мог найти. Для тех, кто хочет сделать это в будущем:

я использовал 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()

8
задан dbr 12 April 2010 в 12:45
поделиться

8 ответов

У вас есть проблема удовлетворения ограничений ; их отношение к NP интересно, потому что они, как правило, NP, но часто не являются NP-полными, т.е. они поддаются полиномиальным решениям.

Как ebo отметило в комментариях, ваша ситуация звучит так, как будто ее можно сформулировать как задача точного покрытия , к которой вы можете применить алгоритм Кнута X . Если вы выберете этот прием, сообщите нам, как он вам подходит.

11
ответ дан 5 December 2019 в 08:00
поделиться

Похоже, у вас есть проблема удовлетворения ограничений .

В вашем случае я бы в первую очередь рассмотрел методы распространения ограничений - вы можете уменьшить проблему до управляемого размера, который путь.

Что произойдет, если никто не соответствует критериям?

3
ответ дан 5 December 2019 в 08:00
поделиться

То, что вы описываете, является «проблемой соседа по комнате», она легко описана в этом тезисе .

Потерпите меня, я ищу лучшие ссылки.

РЕДАКТИРОВАТЬ

Вот еще один довольно плотный тезис .

1
ответ дан 5 December 2019 в 08:00
поделиться

Я не уверен, что ваша проблема - NP, от этого не пахнет, но что бы я сделал на вашем месте, так это упорядочил бы требования к позициям, чтобы вы пытались заполнить наиболее конкретный первый, поскольку на эти должности будет доступно меньше людей, поэтому вам с меньшей вероятностью придется много отказываться. Нет причин, по которым вы не должны комбинировать это с алгоритмом X, алгоритмом чистого Кнута.

1
ответ дан 5 December 2019 в 08:00
поделиться

Что касается меня, я, скорее всего, попытался бы найти сокращение до проблемы сопоставления двудольных графов . Кроме того, доказать, что проблема является NP, обычно намного сложнее, чем оставаться, вы не можете найти полиномиальное решение.

1
ответ дан 5 December 2019 в 08:00
поделиться

Мне кажется, у вас есть пара отдельных проблем, которые было бы намного проще решить:

- выберите одного врача из команды A - выбрать другого врача из любой команды - выберите двух медсестер

Итак, у вас есть три независимые проблемы.

Пояснение: нужно ли вам иметь двух врачей (одного из указанной команды) и двух медсестер, или одного врача из указанной команды, двух медсестер , и еще один, который может быть врачом или медсестрой?

1
ответ дан 5 December 2019 в 08:00
поделиться

Некоторые вопросы:

  1. Является ли цель удовлетворить ограничения точно или только приблизительно (но в максимально возможной степени)?
  2. Может ли человек быть членом нескольких команд?
  3. Каковы все возможные ограничения? (Например, может ли нам понадобиться врач, который является членом нескольких команд?)

Если вы хотите удовлетворить ограничения точно , то я бы упорядочил ограничения по строгости, то есть те, которые труднее всего достичь (например, доктор И команда A в приведенном выше примере) должны быть сначала проверены !

Если вы хотите удовлетворить ограничения приблизительно , тогда его другая история ... вам нужно будет указать какую-то функцию взвешивания / важности, которая определяет, что мы хотели бы иметь, когда мы можем '

1
ответ дан 5 December 2019 в 08:00
поделиться

Я оставлю теорию другим, так как моя математическая смекалка не так уж велика, но вы можете найти такой инструмент, как Cassowary / Cassowary.net или NSolver, полезным для декларативного представления вашей проблемы в виде проблема удовлетворения ограничений, а затем решить ограничения.

В таких инструментах симплекс-метод в сочетании с распространением ограничений часто используется для детерминированного сокращения пространства решений и последующего поиска оптимального решения с учетом функции стоимости. Для больших пространств решений (которые, кажется, неприменимы к размеру проблемы, которую вы указываете), иногда используются генетические алгоритмы.

Если я правильно помню, NSolver также включает в пример кода упрощение реальной задачи включения медсестер. над которым доктор Чун работал в Гонконге. И есть документ о проделанной им работе.

1
ответ дан 5 December 2019 в 08:00
поделиться
Другие вопросы по тегам:

Похожие вопросы: