我正在嘗試撰寫一個演算法,該演算法采用事件串列(在這種情況下,電影放映 - 每部電影通常有不止一個放映,盡管并非總是如此)并回傳事件的最佳可能組合,即一個犧牲最少電影的電影。

我想出了這個我手動應用的演算法,但我試圖把它變成代碼并且遇到了一些麻煩。我所做的(手動)是逐個篩選,檢查它是否與任何其他篩選有沖突。如果是這樣,它將通過選擇兩部電影*(電影 A)中的一部,洗掉電影 A 的所有其他放映,并洗掉電影 A 和電影 B 的首次放映之間的沖突來解決沖突電影B的那個放映。之后,它會尋找另一個電影B的放映,檢查它是否有任何沖突,然后重復這個程序。
* 通常是我目前正在檢查的那部,但某些標準可能會影響決定,例如,如果兩部沖突的電影中的一部在其他地方有免費(無沖突)放映,我會選擇那一部并以這種方式解決沖突。相反,如果兩部電影中的一部電影沒有其他放映,我會選擇那一部。
最終,這個“分支”最終會到達一個免費(無沖突)放映,這意味著整個分支都已解決(即所有涉及的電影都可以在不犧牲任何其他的情況下觀看),或者它會陷入僵局,這意味著這種決策組合并沒有導致完美的解決方案。在這種情況下,將回傳一個遞回級別(即回傳一個決定)并嘗試選擇另一個篩選。如果這不起作用,請回傳另一個級別并重試。如果該分支中沒有導致已解決分支的決策組合,則人類必須做出決定以犧牲導致問題的電影之一。
這幾乎就是我想要撰寫的代碼,我以一種非常意識流的方式寫了一個嘗試,只是想快速把它拿出來,因為我很興奮,沒有想得太遠,只是在問題出現時解決問題向上。它適用于我正在嘗試的電影節,它有點小(同時放映不超過 4 次),但當我在較大的電影節上嘗試時崩潰了(有時同時放映 6 次以上)。它超過了最大堆疊大小,可能是因為代碼中的問題,盡管我不確定它是否可能只是正確運行并且剛剛進入那些遞回級別。在此說明中,不確定使用 while 回圈而不是遞回是否會更好地解決此問題。
昨天我決定放棄我撰寫的演算法并以更好的計劃方式從頭開始,并發現我看到的未來主要問題是:
- 當分支失敗時,演算法“回傳”并切換其先前決策的能力。這是演算法的核心機制,但我正在努力尋找一種編碼它的好方法。在我以前的版本中,我實作了一個“檢查點”系統,如果一個分支失敗,它將恢復到最后一個檢查點并從那里繼續,如果它成功,它將把那個標記為新的檢查點。但這僅適用于頂層,不適用于“內部”決策。
- 大多數時間表將有不止一個解決方案的事實。如果解決方案是完美的(即沒有犧牲任何電影),那么問題就非常小,無論哪種方式,您都不會錯過任何電影,并且最多您將無法在同一部電影的幾場放映中進行選擇。但如果沒有完美的解決方案,現在的選擇可能是在兩部電影之間做出選擇,你真的想看,還是兩部電影你不太關心。這意味著該演算法將需要檢查每一個可能的篩選組合以找到可能的最佳組合,如果沒有完美的解決方案,它將向您展示不同的可能性。但這將是蠻力迫使問題(除非絕對必要)不是我真正想要的。
我將不勝感激有關此事的任何幫助或指導。作為參考,我在 Typescript React Next.js 中寫這個,但我認為這是一個更一般的 CS 問題,所以再次感謝任何幫助。
當前的演算法和模擬資料可以在這里找到:https ://jsfiddle.net/procz/82n3jxLb/
const findBestSchedule = (
screeningData: IScreening[],
movies: IMovie[]
): IScreening[] => {
const debugLog = (type: string, args) => {
if (!DEBUG_LOG) return;
if (type === "process") {
return console.log(
`processing ${findMovie(
movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs - called from ${
args.calledFrom
}, currentArray:`,
args.screenings
);
}
if (type === "conflict") {
return console.log(
`conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs and ${findMovie(
movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs`
);
}
if (type === "free") {
return console.log(
`${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs is free, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
if (type === "recursion") {
return console.log(args.recursionLevel, args.array);
}
if (type === "unsolvable") {
return console.log(
`unsolvable conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} and ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()}, backtracking`
);
}
if (type === "decision") {
return console.log(
`recursion level: ${args.recursionLevel} - choosing ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs, deleting ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()}`
);
}
if (type === "noConflict") {
return console.log(
`no conflicts found for ${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
};
const sortedScreenings = [...screeningData].sort(
(a, b) => b.date.getTime() - a.date.getTime()
);
let latestScreeningArray = sortedScreenings;
let recursionLevel = 0;
let lastSafeArray = latestScreeningArray;
let lastSafeRecursionLevel = recursionLevel;
const processScreening = (
screenings: IScreening[],
screening: IScreening,
calledFrom ? : string
): boolean => {
debugLog("process", {
screening,
calledFrom,
screenings
});
const findConflictingScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
if (!screenings) return [];
return [...screenings].filter(
(otherScreening) =>
screening.id !== otherScreening ? .id &&
screeningsOverlap(screening, otherScreening, movies)
);
};
const conflictingScreenings = findConflictingScreenings(
screenings,
screening
);
if (conflictingScreenings.length) {
const resolveConflict = (
screening: IScreening,
otherScreening: IScreening
): boolean => {
debugLog("conflict", {
screening1: screening,
screening2: otherScreening,
movies,
});
const findNextScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
return [...screenings]
.reverse()
.filter(
(currentScreening) =>
currentScreening.id !== screening.id &&
findMovie(movies, currentScreening).id ===
findMovie(movies, screening).id
);
};
const findFreeScreening = (
screenings: IScreening[],
screening: IScreening
): IScreening => {
return findNextScreenings(screenings, screening).find(
(nextScreening) =>
!findConflictingScreenings(screenings, nextScreening).length
);
};
const freeOtherScreening = findFreeScreening(
latestScreeningArray,
otherScreening
);
const freeScreening = findFreeScreening(
latestScreeningArray,
screening
);
if (freeOtherScreening || freeScreening) {
/* FREE SCREENING */
debugLog("free", {
screening: freeOtherScreening || freeScreening,
movies,
});
latestScreeningArray = deleteAllOtherScreenings(
latestScreeningArray,
freeOtherScreening || freeScreening,
movies
);
return true;
} else {
/* NO FREE SCREENINGS */
const decideAndMoveToNextStep = (
screenings: IScreening[],
screening1: IScreening,
screening2: IScreening
): boolean => {
latestScreeningArray = removeScreening(
deleteAllOtherScreenings(screenings, screening1, movies),
screening2
);
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray,
});
recursionLevel ;
const nextStepOfBranchIsSolvable = processScreening(
latestScreeningArray,
findNextScreenings(screenings, screening2)[0],
`decideAndMoveToNextStep`
);
if (!nextStepOfBranchIsSolvable) {
debugLog("unsolvable", {
movies,
screening1,
screening2
});
latestScreeningArray = screenings;
}
return nextStepOfBranchIsSolvable;
};
const nextScreeningOfOther = findNextScreenings(
latestScreeningArray,
otherScreening
)[0];
if (nextScreeningOfOther) {
debugLog("decision", {
recursionLevel,
movies,
screening1: screening,
screening2: otherScreening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
screening,
otherScreening
);
} else {
const nextScreening = findNextScreenings(
latestScreeningArray,
screening
)[0];
if (nextScreening) {
debugLog("decision", {
recursionLevel,
movies,
screening1: otherScreening,
screening2: screening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
otherScreening,
screening
);
} else {
debugLog("unsolvable", {
movies,
screening1: screening,
screening2: otherScreening,
});
return false;
}
}
}
};
for (let i = conflictingScreenings.length - 1; i >= 0; i--) {
const branchResolved = resolveConflict(
screening,
[...conflictingScreenings].reverse()[i]
);
if (!branchResolved) {
latestScreeningArray = lastSafeArray;
break;
}
}
debugLog("noConflicts", {
movies,
screening
});
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray
});
if (recursionLevel > 0) {
recursionLevel--;
}
return true;
} else {
const updatedScreenings = deleteAllOtherScreenings(
screenings,
screening,
movies
);
latestScreeningArray = updatedScreenings;
if (recursionLevel > 0) {
recursionLevel--;
}
return false;
}
};
for (let i = latestScreeningArray.length - 1; i >= 0; i--) {
if (!!latestScreeningArray[i]) {
lastSafeArray = latestScreeningArray;
lastSafeRecursionLevel = recursionLevel;
processScreening(
latestScreeningArray,
latestScreeningArray[i],
"overarching"
);
}
}
return latestScreeningArray;
};
uj5u.com熱心網友回復:
我建議混合整數編程。NPM 上有一個可用的庫javascript-lp-solver,對于像這樣的輕量級使用來說可能是可以的。
基本思想是為每部電影設定一個 0-1 變數,表示我們是否看到該電影的任何放映,為每個放映設定一個 0-1 變數,表示我們是否看到該放映。我們希望最大化看到的電影數量(或者可能是一些更復雜的線性函式)。
有兩種約束。對于每一次,我們在這段時間內不能參加超過一次的篩查(對于每一次,當時的篩查變數之和小于或等于1)。這是在下面的代碼中使用掃描線演算法處理的。對于每部電影,除非我們參加其中一場放映,否則我們看不到它(對于每部電影,該電影的放映變數之和減去大于或等于 0 的電影變數)。
我在下面的 JavaScript 中實作了這個(很糟糕,因為我不流利,而且這個庫上的 API 也不是最好的)。
const movies = [
{
id: 1,
runtime: 121,
},
{
id: 2,
runtime: 116,
},
{
id: 3,
runtime: 144,
},
{
id: 4,
runtime: 96,
},
{
id: 5,
runtime: 108,
},
{
id: 6,
runtime: 117,
},
{
id: 7,
runtime: 92,
},
{
id: 8,
runtime: 110,
},
{
id: 9,
runtime: 90,
},
{
id: 10,
runtime: 99,
},
{
id: 11,
runtime: 62,
},
{
id: 12,
runtime: 116,
},
{
id: 13,
runtime: 85,
},
{
id: 14,
runtime: 92,
},
{
id: 15,
runtime: 85,
},
{
id: 16,
runtime: 90,
},
{
id: 17,
runtime: 103,
},
{
id: 18,
runtime: 113,
},
{
id: 19,
runtime: 72,
},
{
id: 20,
runtime: 109,
},
{
id: 21,
runtime: 109,
},
{
id: 22,
runtime: 142,
},
{
id: 23,
runtime: 96,
},
{
id: 24,
runtime: 73,
},
{
id: 25,
runtime: 86,
},
{
id: 26,
runtime: 106,
},
{
id: 27,
runtime: 97,
},
{
id: 28,
runtime: 100,
},
{
id: 29,
runtime: 146,
},
{
id: 30,
runtime: 146,
},
{
id: 31,
runtime: 146,
},
{
id: 32,
runtime: 108,
},
{
id: 33,
runtime: 89,
},
{
id: 34,
runtime: 126,
},
{
id: 35,
runtime: 121,
},
{
id: 36,
runtime: 150,
},
{
id: 37,
runtime: 108,
},
{
id: 38,
runtime: 103,
},
{
id: 39,
runtime: 130,
},
{
id: 40,
runtime: 83,
},
{
id: 41,
runtime: 136,
},
{
id: 42,
runtime: 85,
},
{
id: 43,
runtime: 179,
},
{
id: 44,
runtime: 106,
},
{
id: 45,
runtime: 107,
},
{
id: 46,
runtime: 93,
},
{
id: 47,
runtime: 75,
},
{
id: 48,
runtime: 86,
},
{
id: 49,
runtime: 80,
},
{
id: 50,
runtime: 80,
},
];
const screenings = [
{
id: 1,
date: "2021-11-18T23:15:00.000Z",
movieId: 18,
},
{
id: 2,
date: "2021-11-20T14:15:00.000Z",
movieId: 19,
},
{
id: 3,
date: "2021-11-19T21:00:00.000Z",
movieId: 19,
},
{
id: 4,
date: "2021-11-19T15:03:00.000Z",
movieId: 19,
},
{
id: 5,
date: "2021-11-19T23:04:00.000Z",
movieId: 20,
},
{
id: 6,
date: "2021-11-19T17:00:00.000Z",
movieId: 20,
},
{
id: 7,
date: "2021-11-25T20:00:00.000Z",
movieId: 20,
},
{
id: 8,
date: "2021-11-19T14:00:00.000Z",
movieId: 21,
},
{
id: 9,
date: "2021-11-19T20:00:00.000Z",
movieId: 21,
},
{
id: 10,
date: "2021-11-25T17:00:00.000Z",
movieId: 21,
},
{
id: 11,
date: "2021-11-19T21:00:00.000Z",
movieId: 22,
},
{
id: 12,
date: "2021-11-20T18:00:00.000Z",
movieId: 22,
},
{
id: 13,
date: "2021-11-19T16:00:00.000Z",
movieId: 23,
},
{
id: 14,
date: "2021-11-19T14:30:00.000Z",
movieId: 24,
},
{
id: 15,
date: "2021-11-19T23:30:00.000Z",
movieId: 24,
},
{
id: 16,
date: "2021-11-20T19:30:00.000Z",
movieId: 24,
},
{
id: 17,
date: "2021-11-20T14:30:00.000Z",
movieId: 25,
},
{
id: 18,
date: "2021-11-20T20:30:00.000Z",
movieId: 25,
},
{
id: 19,
date: "2021-11-21T22:30:00.000Z",
movieId: 25,
},
{
id: 20,
date: "2021-11-20T14:00:00.000Z",
movieId: 26,
},
{
id: 21,
date: "2021-11-20T20:00:00.000Z",
movieId: 26,
},
{
id: 22,
date: "2021-11-20T15:00:00.000Z",
movieId: 27,
},
{
id: 23,
date: "2021-11-20T21:00:00.000Z",
movieId: 27,
},
{
id: 24,
date: "2021-11-21T14:15:00.000Z",
movieId: 27,
},
{
id: 25,
date: "2021-11-20T18:00:00.000Z",
movieId: 28,
},
{
id: 26,
date: "2021-11-21T00:00:00.000Z",
movieId: 28,
},
{
id: 27,
date: "2021-11-21T17:15:00.000Z",
movieId: 28,
},
{
id: 28,
date: "2021-11-21T21:00:00.000Z",
movieId: 31,
},
{
id: 29,
date: "2021-11-20T21:00:00.000Z",
movieId: 31,
},
{
id: 30,
date: "2021-11-21T00:00:00.000Z",
movieId: 32,
},
{
id: 31,
date: "2021-11-29T00:00:00.000Z",
movieId: 32,
},
{
id: 32,
date: "2021-11-23T18:30:00.000Z",
movieId: 32,
},
{
id: 33,
date: "2021-11-21T14:00:00.000Z",
movieId: 33,
},
{
id: 34,
date: "2021-11-21T20:00:00.000Z",
movieId: 33,
},
{
id: 35,
date: "2021-11-22T22:30:00.000Z",
movieId: 33,
},
{
id: 36,
date: "2021-11-21T18:00:00.000Z",
movieId: 34,
},
{
id: 37,
date: "2021-11-22T23:15:00.000Z",
movieId: 34,
},
{
id: 38,
date: "2021-11-21T20:15:00.000Z",
movieId: 35,
},
{
id: 39,
date: "2021-11-27T21:00:00.000Z",
movieId: 35,
},
{
id: 40,
date: "2021-11-22T15:00:00.000Z",
movieId: 36,
},
{
id: 41,
date: "2021-11-23T00:00:00.000Z",
movieId: 36,
},
{
id: 42,
date: "2021-11-23T14:15:00.000Z",
movieId: 36,
},
{
id: 43,
date: "2021-11-22T13:45:00.000Z",
movieId: 37,
},
{
id: 44,
date: "2021-11-22T18:30:00.000Z",
movieId: 37,
},
{
id: 45,
date: "2021-11-22T21:30:00.000Z",
movieId: 37,
},
{
id: 46,
date: "2021-11-22T17:30:00.000Z",
movieId: 38,
},
{
id: 47,
date: "2021-11-22T23:30:00.000Z",
movieId: 38,
},
{
id: 48,
date: "2021-11-23T16:30:00.000Z",
movieId: 38,
},
{
id: 49,
date: "2021-11-22T21:00:00.000Z",
movieId: 39,
},
{
id: 50,
date: "2021-11-28T18:00:00.000Z",
movieId: 39,
},
{
id: 51,
date: "2021-11-23T18:00:00.000Z",
movieId: 40,
},
{
id: 52,
date: "2021-11-27T21:30:00.000Z",
movieId: 40,
},
{
id: 53,
date: "2021-11-24T18:00:00.000Z",
movieId: 41,
},
{
id: 54,
date: "2021-11-23T18:00:00.000Z",
movieId: 41,
},
{
id: 55,
date: "2021-11-25T18:00:00.000Z",
movieId: 41,
},
{
id: 58,
date: "2021-11-23T21:00:00.000Z",
movieId: 43,
},
{
id: 59,
date: "2021-11-24T21:00:00.000Z",
movieId: 43,
},
{
id: 60,
date: "2021-11-24T14:30:00.000Z",
movieId: 44,
},
{
id: 61,
date: "2021-11-24T20:30:00.000Z",
movieId: 44,
},
{
id: 62,
date: "2021-11-25T16:30:00.000Z",
movieId: 44,
},
{
id: 63,
date: "2021-11-25T21:00:00.000Z",
movieId: 45,
},
{
id: 64,
date: "2021-11-26T15:00:00.000Z",
movieId: 45,
},
{
id: 70,
date: "2021-11-24T15:00:00.000Z",
movieId: 48,
},
{
id: 71,
date: "2021-11-24T21:00:00.000Z",
movieId: 48,
},
{
id: 72,
date: "2021-11-26T00:00:00.000Z",
movieId: 48,
},
{
id: 76,
date: "2021-11-24T14:00:00.000Z",
movieId: 50,
},
{
id: 77,
date: "2021-11-24T20:00:00.000Z",
movieId: 50,
},
{
id: 78,
date: "2021-11-27T17:00:00.000Z",
movieId: 50,
},
];
let model = {
optimize: "movieSeen",
opType: "max",
constraints: {},
variables: {},
ints: {},
};
let constraintId = 1000;
for (const movie of movies) {
constraintId;
model.constraints[constraintId] = { max: 1 };
model.variables["m" movie.id] = { movieSeen: 1 };
model.variables["m" movie.id][constraintId] = 1;
constraintId;
model.constraints["sm" movie.id] = { min: 0 };
model.variables["m" movie.id]["sm" movie.id] = -1;
}
for (const screening of screenings) {
constraintId;
model.constraints[constraintId] = { min: 0 };
model.variables["s" screening.id] = { constraintId: 1 };
model.variables["s" screening.id]["sm" screening.movieId] = 1;
model.ints["s" screening.id] = 1;
}
let runtimes = {};
for (const movie of movies) {
runtimes[movie.id] = movie.runtime;
}
let events = [];
for (const screening of screenings) {
const start = Date.parse(screening.date);
events.push({ date: start, isStart: true, id: screening.id });
const finish = start runtimes[screening.movieId] * 60 * 1000;
events.push({ date: finish, isStart: false, id: screening.id });
}
events.sort(function (a, b) {
return a.date - b.date;
});
let previousIsStart = false;
let nowPlaying = {};
for (const event of events) {
if (event.isStart) {
nowPlaying[event.id] = true;
previousIsStart = true;
} else {
if (previousIsStart) {
constraintId;
model.constraints[constraintId] = { max: 1 };
for (const id of Object.keys(nowPlaying)) {
model.variables["s" id][constraintId] = 1;
}
}
delete nowPlaying[event.id];
previousIsStart = false;
}
}
let solver = require("javascript-lp-solver");
let results = solver.Solve(model);
console.log(results);
輸出:
{
feasible: true,
result: 27,
bounded: true,
isIntegral: true,
s1: 1,
s64: 1,
s12: 1,
s15: 1,
s42: 1,
s20: 1,
s24: 1,
s29: 1,
s31: 1,
s37: 1,
s19: 1,
s46: 1,
s51: 1,
s53: 1,
s58: 1,
s71: 1,
s13: 1,
s3: 1,
s8: 1,
s34: 1,
s7: 1,
s26: 1,
s39: 1,
s43: 1,
s49: 1,
s76: 1,
s62: 1,
m18: 1,
m19: 1,
m20: 1,
m21: 1,
m22: 1,
m23: 1,
m24: 1,
m25: 1,
m26: 1,
m27: 1,
m28: 1,
m31: 1,
m32: 1,
m33: 1,
m34: 1,
m35: 1,
m36: 1,
m37: 1,
m38: 1,
m39: 1,
m40: 1,
m41: 1,
m43: 1,
m44: 1,
m45: 1,
m48: 1,
m50: 1
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qukuanlian/478421.html
標籤:javascript 算法 计算机科学
上一篇:實作以下結果的最佳方法是什么?
