Поиск наиболее оптимального пути преобразования старого HTML в новый HTML ⇐ Javascript

[Anonymous]

Учитывая 2 массива, которые представляют список элементов HTML в старом HTML и New HTML соответственно, мне нужно найти различие между двумя массивами.
Что я делаю в настоящее время:

[*] Создайте 2D -минус матрицу стоимости с использованием динамического программирования с использованием Levenshtein Distance < /li>
Переверните матрицу снизу вверху слева и найдите Путь < /li>
< /ol>
Но это не всегда приводит к оптимальному пути (в основном потому, что я принимаю локально оптимальные решения, которые оказываются под оптимальными во всем мире). Итак, я хочу знать, как подходить к этому? или не может быть истин.

Код: Выделить всё

row       = old.length+1;
column    = current.length+1;
diff      = []
function createMatrix() {
matrix = new Array(row);
for (var i = 0; i < row; i++) {
matrix[i] = new Array(column);
}
//fill the 0th row and column
for (var i = 0; i < row; i++) {
matrix[i][0] = i;
}
for (var j = 0; j < column; j += 1) {
matrix[0][j] = j;
}
//calculate min operations
for (var i = 1; i < row; i++) {
for (var j = 1; j < column; j++) {
var a = old[i - offset];
var b = current[j - offset];
var subDistance = (a.hashVal == b.hashVal) ? 0 : 10e6;
var costReplace = matrix[i - 1][j - 1] + subDistance * a.elementCount + subDistance * b.elementCount;
var costRemoved = matrix[i - 1][j] + a.elementCount;
var costInserted = matrix[i][j - 1] + b.elementCount;
matrix[i][j] = Math.min(costReplace, costRemoved, costInserted);
}
}
}

функция, которая находит путь для создания diff:

Код: Выделить всё

function traceBack(){
var i,j;

for(i=row-1,j = column-1;i>0&&j>0;){
var top = matrix[i-1][j];
var topLeft = matrix[i-1][j-1];
var left = matrix[i][j-1];
if(topLeft== matrix[i][j] && topLeft 0){
(current[j-offset]).status = 'inserted';
diff.unshift(current[j-offset]);
j--;
}
}

Несколько моментов:

Входные строки HTML преобразуются в объект DOM с помощью библиотеки htmlparser
[*]Некоторая базовая предварительная обработка выполняется над объектами DOM.
[*]Объекты сводятся в один список (дочерняя цепочка, сглаживается)
[*]createMatrix называется ..


Подробнее здесь: https://stackoverflow.com/questions/793 ... o-new-html