Библиотека для поиска по дереву для задач комбинаторной оптимизации

Question

Я замечаю, что некоторые из"сложные" комбинаторные проблемы, с которыми я сталкиваюсь, могут быть выражены в терминах некоторого типа поиска по дереву, такого как обрезка альфа-бета или поиск луча,или аналогичный алгоритм.Однако их программирование похоже на повторяющееся кодирование одних и тех же вещей, а также довольно легко совершать ошибки.Мне кажется, должна быть библиотека, которая реализует эти алгоритмы, и все, что мне нужно попросить написать, это

1. кодировка для решения, то есть, как получить более конкретное решение из неполногорешение.Это даст структуру дерева / графика.
2. При условии частичного решения, как получить максимальную / минимальную стоимость и, возможно, оценку стоимости.
3. Первоначальное решение / частичное решение.
4. Может быть, какое-то решение для проверки.

Извините, я не дал никакого конкретного кода, но думаю, что объяснил проблему.Если я могу написать код для функций, описанных выше, разве я не смогу легко запустить несколько алгоритмов поиска по дереву / графику?Есть ли удобная библиотека / фреймворк, которая легко это поддерживает?Я бы хотел, чтобы это было на Python или C / C ++, но было бы интересно услышать любые предложения.

Редактировать: Точнее, я говорю об информированных алгоритмах поиска по дереву.

Answer 1

Fuego - это платформа для поиска по дереву Монте-Карло с открытым исходным кодом (в отличие от поиска по дереву альфа-бета), которая может предназначаться для игр с полной информацией для двух игроков (изначально созданных для игры в Го).Он может быть даже более общим, чем это.

http://fuego.sourceforge.net/

Редактировать: я только что узнал, что он также имеет альфа-бета-поисковик.Вот недавняя статья: http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf

Answer 2

QuickGraph

Для всех, кто хочет перейти на .Net, взгляните на библиотеку QuickGraph с открытым исходным кодом для всей обработки ваших графиков / деревьев.Он аккуратно разделяет все понятия, связанные с представлением графа, алгоритмами, мутациями и представлением.У него много точек расширения, поэтому он должен поддерживать большинство задач, связанных с графированием.

[РЕДАКТИРОВАТЬ] Набор алгоритмов, поставляемых с QuickGraph, не включает в себя обрезку альфа-бета или поиск луча в данный момент, хотя его раздел «Поиск» алгоритмов включает в себя 11 других методов, которые обеспечивают достаточное руководство для реализации вашего любимого обходаалгоритм, и со временем я бы предположил, что он будет поддерживать альфа-бета и луч.

объявление.1 Он действительно удовлетворяет вашему первому критерию, поскольку в него можно вставить функцию делегата, которая возвращает несколько более конкретных решений (т. Е. Соседних узлов) на основе неполного решения (т. Е. Текущего узла).Это обрабатывается DelegateImplicitGraph (и вариациями) и, как предполагается, эффективно использует память, поскольку предотвращает одновременное хранение всего пространства поиска в памяти. объявление.2 Кроме того, алгоритмы могут принимать пользовательские делегаты, такие как макс / мин / ожидаемая стоимость (см. AStarShortestPathAlgorithm).Это удовлетворяет вашему второму критерию.

Таким образом, QuickGraph помогает структурировать вашу проблему, предоставляет алгоритмы вставки для различных типов проблем и позволяет улучшить ее, предлагая новые алгоритмы.

Answer 3

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

Вы говорите о «частичных решениях». Значит ли это, что рассматриваемые вами проблемы имеют перекрывающиеся подзадачи? Если так, то звучит так, будто вы спрашиваете, как сделать общее динамическое программирование . Все, что на самом деле означает, - это построение функции с помощью последовательных шагов, решение более простых версий проблемы и затем повторение. В этой журнальной статье Mathematica .

есть несколько хороших примеров.

Рассматривали ли вы Пролог ? Это не фреймворк, но алгоритм поиска, если хотите, встроен в язык. Можно написать очень общие решения для программирования ограничений , используя в качестве основы что-то вроде Prolog. В Python есть библиотека с ограничениями python , что довольно неплохо - я использовал ее в прошлом.

Answer 4

Boost имеет Libra Graph Boost (BGL) .В Руководстве пользователя библиотеки Boost Graph есть пример по проблеме обхода Найта с использованием неявных графов.

Answer 5

Я нашел Python-код Питера Норвига для информированного и неинформированного поиска онлайн. Он поддерживает поиск A-star и может использоваться для программирования общих проблем из того, что я вижу. Интересно, достаточно ли это быстро или может быть расширено для поиска луча, ветвления и привязки и т. Д.