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