Я создал алгоритм A * для JavaScript. Важно то, что он должен искать самый длинный путь, а не самый короткий. Когда путь заканчивает поиск, я просто хочу получить глубину пути / его длину. Алгоритм просто возвращает максимальную длину вместо пути.
При отладке результата я думаю, что этот алгоритм просто возвращает значение эвристики.
У меня есть объекты сцены с идентификаторами и объекты активности, которые соединяют две стадии, удерживая fromId и toId.
Пример:
У меня есть идентификаторы статусных объектов
и деятельность
Я ожидал такого результата:
но результат, который я получаю,
Why do I think I can use the A* for the longest path?
Well the A* compares distances and takes the lower one. It should be possible to take the higher distance with higher cost by changing the compare statement.
Я привожу здесь рабочий пример кода
// #########################################
// My initializer script with some fake data
// #########################################
$(document).ready(() => {
const path = new Path(activities, 1);
for (let i = 0; i < stages.length; i++) {
const currentStage = stages[i];
const currentStageId = currentStage.id;
const currentDistance = path.getMaximumDistance(currentStage);
console.info(`id: ${currentStageId} distance: ${currentDistance}`);
}
});
const stages = [
new Stage(1),
new Stage(2),
new Stage(3),
new Stage(4),
new Stage(5)
];
function Stage(id) {
this.id = id;
}
const activities = [
new Activity(1, 2),
new Activity(1, 3),
new Activity(2, 3),
new Activity(3, 5),
new Activity(5, 1)
];
function Activity(fromId, toId) {
this.fromId = fromId;
this.toId = toId;
}
// #########################################
// The A* class
// #########################################
function Path(activities, initialId) {
this.getMaximumDistance = (targetStage) => {
var me = this;
var targetId = targetStage.id;
var openList = [];
var closedList = [];
this.addNodeToList(openList, this.createNode(initialId, this.activities));
let maxDistance = 0;
while (openList.length > 0) {
var currentNode = openList[this.getHighestCostIndex(openList)];
if (currentNode.id === targetId) {
maxDistance = this.getPathLength(currentNode);
break;
}
this.removeNodeFromList(openList, currentNode);
this.addNodeToList(closedList, currentNode);
currentNode.neighbourIds.forEach(id => {
var neighbour = me.createNode(id, me.activities);
let lookUpTableElement;
if (!me.listContainsNode(closedList, neighbour)) {
var tempIncrementalCost = currentNode.incrementalCost + 1;
if (me.listContainsNode(openList, neighbour)) {
if (tempIncrementalCost < neighbour.incrementalCost) {
neighbour.changeIncrementalCost(tempIncrementalCost);
}
} else {
neighbour.changeIncrementalCost(tempIncrementalCost);
me.addNodeToList(openList, neighbour);
}
for (var i = 0; i < me.lookUpTable.length; i++) {
var currentLookUpTableElement = me.lookUpTable[i];
if (currentLookUpTableElement.id === neighbour.id) {
lookUpTableElement = currentLookUpTableElement;
}
}
var heuristic = lookUpTableElement ? lookUpTableElement.cost : 0;
neighbour.changeHeuristic(heuristic);
neighbour.setParent(currentNode);
}
});
}
return maxDistance;
};
this.createNode = (id, activities) => {
return new PathNode(id, activities);
};
this.getHighestCostIndex = (openList) => {
let highestCostIndex = 0;
for (let i = 0; i < openList.length; i++) {
if (openList[i].totalCost > openList[highestCostIndex].totalCost) {
highestCostIndex = i;
}
}
return highestCostIndex;
};
this.addNodeToList = (list, node) => {
list.push(node);
};
this.listContainsNode = (list, node) => {
return list.some(x => x.id === node.id);
};
this.removeNodeFromList = (list, node) => {
var index = list.indexOf(node);
list.splice(index, 1);
};
this.getPathLength = (node) => {
let currentNode = node;
let counter = 0;
while (currentNode.parent) {
currentNode = currentNode.parent;
counter++;
}
return counter;
};
this.activities = activities;
this.lookUpTable = new LookUpTable(this.activities, initialId).table;
}
// #########################################
// Node class for the A*
// #########################################
function PathNode(id, activities) {
this.getNeighbourIds = (activities) => {
return activities
.filter(x => x.fromId === id)
.map(x => x.toId);
};
this.setParent = (parentNode) => {
this.parent = parentNode;
};
this.changeHeuristic = (heuristic) => {
this.heuristic = heuristic;
this.updateTotalCost();
};
this.changeIncrementalCost = (incrementalCost) => {
this.incrementalCost = incrementalCost;
this.updateTotalCost();
};
this.updateTotalCost = () => {
this.totalCost = this.incrementalCost + this.heuristic;
};
this.id = id;
this.heuristic = 0;
this.incrementalCost = 0;
this.totalCost = 0;
this.parent = null;
this.neighbourIds = this.getNeighbourIds(activities);
}
// #########################################
// The heuristic code
// #########################################
function LookUpTable(activities, originId) {
this.getLookUpTable = (originId) => {
const me = this;
const lookUpTable = [];
let currentLevel = 0;
let openList = [];
this.addStage(openList, originId, currentLevel);
while (openList.length > 0) {
var lookUpTableElements = openList.filter(openNode => openNode.cost <= currentLevel);
lookUpTableElements.forEach(lookUpTableElement => {
this.addStage(lookUpTable, lookUpTableElement.id, currentLevel);
var neighbours = activities.filter(targetActivity => targetActivity.fromId === lookUpTableElement.id);
neighbours.forEach(neighbour => {
var neighbourId = neighbour.toId === lookUpTableElement.id ? neighbour.fromId : neighbour.toId;
if (!lookUpTable.some(x => x.id === neighbourId) && !openList.some(x => x.id === neighbourId)) {
me.addStage(openList, neighbourId, currentLevel + 1);
}
});
});
openList = openList.filter(x => x.cost !== currentLevel);
currentLevel++;
}
return lookUpTable;
};
this.addStage = (array, stageId, level) => {
array.push({
id: stageId,
cost: level
});
};
this.activities = activities;
this.table = this.getLookUpTable(originId);
}<script src = "https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>Что не так с моим алгоритмом A * в том, что он возвращает правильное эвристическое значение вместо максимального расстояния?
Important note: If someone got a better idea for finding the maximum distance between these connections please let me know!



![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)


В общем, алгоритмы поиска кратчайшего пути не могут быть настроены так, чтобы возвращать (простой) самый длинный путь в данном графе.
Дополнительно нахождение простого (нециклического) самый длинный путь NP-сложен.
В вашем случае стоимость каждого ребра равна 1, к сожалению, это не улучшает ситуацию. Даже если бы вы знали, что можете достичь всех вершин, вы бы в конечном итоге искали Гамильтон Путь, который является NP-Complete.
Я предлагаю посмотреть на аппроксимационные алгоритмы для проблемы с самым длинным путем.
так ты думаешь, для этого не будет решения? Кроме алгоритмов аппроксимации
В общем, действенного (!) Решения для этого нет. Возможно, у вас есть особая настройка, в которой это неверно (например, когда ваш граф представляет собой дерево, блочный граф, кактусы, граф двудольных перестановок или граф Птолемея), но из вашего описания проблемы трудно сказать. Когда у вас всего несколько вершин (статусные объекты <10), вы можете обойтись без перебора.
извините, что вы установили startId в качестве параметра. Каждый результат индивидуален. Для вашего примера 2 будет startId, и вы проверяете targetId 1