Есть поле <30x30. Мы можем по этому полю проводить линии по вертикали и горизонтали, которые могут пересекаться.
Пример возможного расположения линий
Правила следующие:
Каждая клетка имеет тип 0, 1 или 2. Каждая линия тоже имеет тип 0, 1 или 2.
Если линия проходит через свой тип, то штраф равен 0. Если через соседний (0 чере
1, 1 через 2 или наоборот), то штраф равен 1. Если через дальний (0 через 2 или наоборот), то штраф равен 5.
Начисляется дополнительный штраф за пересечение линий равный количеству линий умноженому на константу N, при этом одним пересечением считается одна общая клетка.
На вход дается: константа N, поле с указанием типов клеток, параметры каждой линий с указанием начала, конца и типа.
Нужно провести заданые линии так, чтобы штраф был минимальным.
Время работы: вообще меня устроит и 5 минут, но лучше было бы уложиться в несколько секунд (хотя бы для полей 10x10).
Задача вроде простая (на графы), если бы не условие о штрафе за пересечения. Не зна
что делать именно с ним, так что прошу подсказать по поводу него. Может быть есть какие-то готовые алгоритмы для подобных вещей, о которых я не знаю.
Ответы
Ответ 1
Если я правильно понимаю, вам нужно оптимизировать путь для каждой из линий. Учте
что вариантов проведения каждой линии будет (для n>2, где n это ребро поля) 4^((n-2)^2
+ 4*3^(n-2) + 8. Таким образом, я бы лично искал не "лучший путь" - выдаюший кратчайшее из возможных "растояний", так как поиск такого пути может потребовать ОЧЕНЬ МНОГО времени ,а "хороший путь" - такой, какой мы можем найти за ограниченное наперед время, но который не является обязательно "лучшим из возможных".
Пожалуй тут я вижу два подхода, что то вроде шахматной алфа-беты, правда тут прийдется поломать голову над функцией оценки. Либо, что нибудь типа муравьиного алгоритма.
Ответ 2
А почему бы не воспользоваться волновым алгоритмом? Только в классической виде необходим
найти расстояние, Вам же надо минимизировать штраф. Например, представим поле 5х5 с начальными данными для линии (2,3), (4,1), 1. Получится следующая картина:
Ответ 3
Используем бинпоиск по ответу.
Т. е. ограничиваем максимальный штраф и запускаем решение задачи с таким ограничением
Если решение найдено, то за стоимость не большую данной построить можно. При этом решение не обязано гарантировать минимальность - оно лишь гарантирует существование или несуществование.
Минимальное значение будет обеспечено бинпоиском.
Алгоритм Дейкстры скорее всего к данной задаче неприменим.
Там есть условие, что если два пути суммарно короче, то лучше пройти по ним, а тут есть штраф за пересечение, который влияет на стоимость.
Возникает мысль свести эту задачу к потокам на графе
Добавляем общий исток и общий сток, пытаемся прогнать поток с величиной, равной лимиту, перебираемому в бинпоиске.
Допускаю, что эта идея может быть неверна.
Допускаю, что от бинпоиска можно отказаться (хотя сомнительно).
На этом пока всё.
Ответ 4
Ваша задача состоит из двух:
Аккуратно по заданному полю построить взвешенный граф. Это банальная вычислительная комбинаторика.
Примененить алгоритм Дейкстры.
Ответ 5
Искать пути можно алгоритмом Дейкстры, но сначала для каждой линии нужно построит
граф особого вида, назовем его граф Д. В узлах графа Д будут либо отдельные клетки с
штрафами больше 0, либо множества сопряженных "своих" клеток со штрафами 0. Множеств
"своих" клеток должны включать клетки в каждую из которох можно попасть не проходя через "чужие", тут надо следить чтобы в эти области не попадали диагональные клетки. Путь в штрафной узел будет равен штрафу ее клетки, путь в нулевые узлы будет равен собственно 0. Штрафы естественно считаются относительно целевой линии.
После того как Дейкстра отработает, нужно дополнительно в каждом "своем" узле, вошедшем в путь, строить путь от входа до выхода. Это не сложно сделать волновым алгоритмом.
После того как пути построены нужно искать пересечения и выполнять пересчет начина
с перестроения графа Д. Перестроение будет заключаться в увеличении штрафов в "чужих" узлах и разбиении "своих" в соответсвии с пересечениями.
Тут мы подходим к главной проблеме - какие линии пересчитывать!
Забудем Дейкстру. Будем применять вариацию минимакса алгоритм альфа-бета отсечени
(подробнее или здесь). Для альфа-бета отсечения (АБС) требуется строить дерево состояний
Эти состояния будут представлены графами Д для всех линий сразу. Каждое ветвление дерева АБС это выбор очередного узла для одной из линий. На каждом ветвлении АБС граф Д нужно перестраивать и пересчитывать штрафы.
Для АБС очень важны эвристики, вот несколько пришедших мне в голову:
В случае трех линий 0, 1 и 2, линия 1 имеет то преимущество что ее штраф за чужи
клетки всегда равен 1. Поэтому при выборе линии для пересчета нужно выбирать линию 1 так как вероятность увеличения штрафа ниже.
Тоже самое с другого боку, можно подсчитывать количество клеток каждого типа и таким образом получать вероятность увеличения штрафа при пересчете линии.
При построении пути, если встречается штрафной узел, можно подсматривать в "чужой" граф Д для :
определения размеров "чужой" области,
быстрого построения пути до более "дешевых" узлов тем же волновиком,
а так же для определения расстояния до концов "чужой" линии предполагая что вероятность пересечения в близких узлах выше.
Ответ 6
Может быть вначале вообще не учитывать штрафы за пересечения и Дейкстрой пройтис
по графу и провести линии. Если на выходе мы не получили пересечений (за исключение
точки отправки и точки назначения) то алгоритм закончен. Если пересечения есть, то добавляе
в граф дополнительные штрафы за пересечения в узлы, где пролегают текущие линии. Теперь проходимся декстрой снова для каждой линии по очереди, если пути не поменялись, алгоритм закончен, если поменялись снова повторяем этот цикл. В итоге мы придем к той ситуации, когда сократить путь будет уже невозможно и линии останутся неизменными. Нужно не забывать обновлять штрафы за пересечения после каждой дейкстры над каждой линией.
Комментариев нет:
Отправить комментарий