Доработать скрипт поиска путей в матрице
Необходимо доработать скрипт поиска путей в матрице с применением алгоритма ветвей и границ. База уже написана и снабжена хорошими комментариями https://github.com/TheSaturn/BranchAndBound ( http://habr.x1site.ru/ ) - нужно взять её за основу.
Задачи:
1. Реализовать поиск кратчайшего замкнутого пути через все вершины от выбранной стартовой точки (задача Коммивояжёра) (решение с применением алгоритма ветвей и границ);
2. Поиск кратчайшего пути между двумя выбранными точками через все остальные (решение с применением алгоритма ветвей и границ);
3. Поиск кратчайшего пути от выбранной точки через все остальные. Тут алгоритмы или А*, или Гамильтонов, или предлагайте своё решение.
4. Сделать отдельный инпут в который при необходимости можно будет ввести ограничитель максимальной длины пути. Если этот параметр будет задан, то для задачи 1 "Поиск кратчайшего пути из любой точки до всех остальных" - алгоритм должен будет остановиться на точке не выходящей за ограничение; для задачи 2 - искать путь Коммивояжёра не выходящий за ограничение (за счет пропуска некоторых точек), но должно быть посещено максимум точек на пути; для задачи 3 - должен быть найден путь лежащий между двумя точками в рамках заданного ограничения, но тоже с максимальным количеством пройденных точек.
Детали:
- Во всех задачах (1-3) должны быть пройдены все точки;
- Каждая точка может быть пройдена только один раз;
- Число знаков после запятых 3;
- Таблица должна быть подключаемой через CSV - сейчас это реализовано из php файла;
- Скрипт должен рассчитывать таблицу произвольной размерности так чтобы я мог менять данные в таблице как хочу или просто подключать другой файл;
- Мы не делаем несколько примеров на одной странице, а переключаемся между алгоритмами с помощью radio-button;
- мы по прежнему в соответствии с заданием реализуем выбор стартовых и там где надо финальных точек вручную (например из select).
Оплата:
Оплата по схеме с протекцией - перевожу деньги вам на электронный кошелек (например Яндекс.Деньги), после того как сдаёте работу проверяем, в случае наличия багов правим - я отдаю код на транзакцию. Можно любым другим способом.