Arhn - архитектура программирования

Использование кратчайшего пути из одного источника для обхода шахматной доски

Скажем, у нас есть шахматная доска размера n x n (или, другими словами, матрица), и у каждого квадрата есть свой вес. Фигура может двигаться по горизонтали или вертикали, но не по диагонали. Стоимость каждого хода будет равна разнице двух клеток на шахматной доске. Используя алгоритм, я хочу найти минимальную стоимость перемещения одной шахматной фигуры с квадрата (1,1) на квадрат (n,n), который имеет временную сложность в наихудшем случае за полиномиальное время.

Можно ли использовать алгоритм дикстры для решения этой проблемы? Сможет ли мой алгоритм, приведенный ниже, решить эту проблему? Diijkstras уже можно запускать за полиномиальное время, но что делает его сложным на этот раз?

Псевдокод:

У нас есть некоторое пустое множество S, некоторое целое число V и входной невзвешенный граф. После этого мы заполняем матрицу смежности, показывающую стоимость ребра без вершин, взвешенных по бесконечности, и, пока матрица не выбрала все вершины, мы находим вершину, и если значение квадрата меньше квадрата, на котором мы сейчас находимся, двигаемся к этому квадрату и обновите V с разницей между двумя квадратами и обновите S, отмечая каждую посещенную вершину. Мы делаем этот процесс до тех пор, пока не останется вершин.

Спасибо.

graph algorithm matrix shortest-path chess
12.10.2015

  • Could dikstras algorithm be used to solve this? предполагая, что различия берутся по абсолютной величине, тогда да 13.10.2015
  • @svs Но если бы я хотел это за полиномиальное время, мне пришлось бы использовать ненаправленную или направленную реализацию? 13.10.2015
  • это не имеет значения. временная сложность одинакова 13.10.2015
  • @svs Я знаю, что это сложно реализовать, но что может заставить такой алгоритм иметь временную сложность полиномиального времени? 13.10.2015
  • algorithm like this если вы говорите о своем алгоритме, мне трудно его понять. Дейкстры будет достаточно. Вы также можете использовать динамическое программирование для решения вашей проблемы. Сложность — O(MN), где MxN — размер вашей доски. 13.10.2015
  • Проверьте это и посмотрите, полезно ли оно. 13.10.2015
  • Итак, вы хотите пройти от А до Б по наклонному ландшафту и избежать ненужных подъемов и спусков? 13.10.2015
  • @ m69 по сути да, но я хочу иметь возможность ходить по горизонтали или вертикали, если это возможно, к следующей клетке, чтобы добраться до (n, n), не пересекая по диагонали, но трудная часть, которую я придумал, это как сделать полином наихудшего случая. 13.10.2015
  • @svs Извините, если это немного сбивает с толку, но в основном я хочу взять неориентированный граф, пустой набор и подсчет, чтобы добавить веса из разницы в квадратах. Делаем это до тех пор, пока вершин не останется. Что нужно сделать, чтобы сделать это за полиномиальное время? 13.10.2015
  • Просто для ясности: спуститься из А в Б так же дорого, как подняться из В в А? 13.10.2015
  • @m69 Зависит от веса. Если A имеет больший вес, связанный с, то нет. Требуется менее жадный подход, когда, если мой конечный результат будет дешевле, я выбираю этот путь. Например, если S-›b-›a-›g дешевле, чем S-›a-›c-›b-›g, я выберу первый вариант. 14.10.2015

Ответы:


1

Поскольку вы пытаетесь найти путь с минимальной стоимостью, вы можете использовать для этого метод Дейкстры. Поскольку Дейкстра в худшем случае равен O(|E| + |V|log|V|), где E — количество ребер, а V — количество вершин в графе, это удовлетворяет вашему требованию полиномиальной временной сложности.

Однако, если ваш алгоритм учитывает только затраты, связанные с начальным и конечным квадратом хода, а не с промежуточными узлами, то вы должны соединить все возможные начальные и конечные квадраты вместе, чтобы можно было «сокращать путь» вокруг промежуточных узлов. .

13.10.2015
  • большое спасибо, я ценю помощь! Возможно ли, чтобы |V| быть в квадрате? Другими словами, будет ли |V|^2 временной сложностью наихудшего или наилучшего случая? 14.10.2015
  • Вы хотите сделать алгоритм менее эффективным? V log V - лучшая временная сложность, чем V ^ 2. 14.10.2015
    • Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..