javascript 如何使用偏好算法获得每一步的最小和最大比较可能性?

nkhmeac6  于 2023-10-14  发布在  Java
关注(0)|答案(1)|浏览(65)

我正在做一个比较应用程序,为了用户体验,我想实现一个进度条让用户看到。现在,根本不可能确切地知道需要进行多少次比较,所以在每次比较之后获得最小和最大比较的范围是理想的,因为我可以动态地向用户保证他们正在接近他们的目标。
我使用的算法是this算法的TypeScript版本,增加了一个函数calculateMinMax(),它返回给定长度的最小值和最大值。经过一段时间(令人尴尬的时间),我发现最小比较值总是C(n) = Math.floor(Math.log2(n)) + C(n - 1),而最大比较值总是C(n) = Math.ceil(Math.log2(n)) + C(n - 1)。代码如下:

  1. class PrefList {
  2. size: number
  3. items: { item: number, equals: number[] }[] = [{ item: 0, equals: [] }]
  4. current = { item: 1, try: 0, min: 0, max: 1 }
  5. iteration: number = 0
  6. estimated: { min: number, max: number } = { min: 0, max: 0 }
  7. constructor(n: number)
  8. constructor(n: Array<any>)
  9. constructor(n: number | Array<any>) {
  10. this.size = (typeof n == "number") ? n : n.length
  11. const [min, max] = this.calculateMinMax(this.size)
  12. this.estimated = {min, max}
  13. }
  14. addAnswer(pref: -1 | 0 | 1): void {
  15. this.iteration++
  16. if (pref == 0) {
  17. this.items[this.current.try].equals.push(this.current.item)
  18. this.current = { item: ++this.current.item, try: 0, min: 0, max: this.items.length }
  19. } else {
  20. if (pref == -1) this.current.max = this.current.try
  21. else this.current.min = this.current.try + 1
  22. if (this.current.min == this.current.max) {
  23. this.items.splice(this.current.min, 0, { item: this.current.item, equals: [] })
  24. this.current = { item: ++this.current.item, try: 0, min: 0, max: this.items.length }
  25. }
  26. }
  27. }
  28. getQuestion(): { a: number, b: number } {
  29. if (this.current.item >= this.size) return null
  30. this.current.try = Math.floor((this.current.min + this.current.max) / 2)
  31. return ({ a: this.current.item, b: this.items[this.current.try].item })
  32. }
  33. getOrder() {
  34. var index = []
  35. for (var i in this.items) {
  36. index.push(this.items[i].item)
  37. for (var j in this.items[i].equals) {
  38. index.push(this.items[i].equals[j])
  39. }
  40. }
  41. return (index)
  42. }
  43. calculateMinMax(v: number): [number, number] {
  44. if (v <= 1) return [0, 0]
  45. const val = Math.log2(v)
  46. const rest = this.calculateMinMax(v - 1)
  47. return [Math.floor(val) + rest[0], Math.ceil(val) + rest[1]]
  48. }
  49. }

现在,这个函数在初始化类时工作,但这就是它的作用。我尝试了多种方法来处理每一步的最小值和最大值的更新(每次进行比较时),但我无法弄清楚。我很确定选择第一个和第二个之间有联系。选择第二个,因为在每次比较中选择第一个将给你给予最小的比较量,而在每次比较中选择第二个将给你给予最大的比较量,但这就是我所得到的。我真的不知道该怎么办。任何和所有的帮助是赞赏。
下面是一个比较的例子(原始测试的稍微修改版本)。在这个例子中,你有一个数组,里面有8种水果,你可以在每种水果中选择一种。下面是测试代码:

  1. var array = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry"]
  2. var t = new PrefList(array.length), q
  3. while (q = t.getQuestion()) {
  4. console.log(t.iteration + ". " + array[q.a] + " or " + array[q.b] + "?")
  5. const response = prompt("")
  6. var answer = parseInt(response)
  7. console.log("→ " + [array[q.a], "whatever", array[q.b]][answer + 1])
  8. t.addAnswer(answer as -1 | 1)
  9. console.log("")
  10. }
  11. var index = t.getOrder()
  12. console.log("\nLIST IN ORDER:")
  13. for (var i in index) console.log("\t" + (parseInt(i) + 1) + ". " + array[index[i]])

当运行上面的代码时,你可以通过输入1来选择左边的选项,通过输入-1来选择右边的选项(除了第一个选项,在这种情况下,1对应于右边的项目,-1对应于左边的项目)。

rta7y2nd

rta7y2nd1#

我想通了。为了在当前步骤中找到最小值和最大值比较,必须存储在前面步骤中进行的比较,并在计算最小值和最大值时使用它们。

说明

为了更好地理解这一点,我们可以分解最小值和最大值函数:

  1. function calculateMinMax(v: number): [number, number] {
  2. // Return [0, 0] since log2(1) = 0
  3. if (v <= 1) return [0, 0]
  4. // Get the log2 of the current number
  5. const val = Math.log2(v)
  6. // Recursive call (can be ignored for now)
  7. const rest = this.calculateMinMax(v - 1)
  8. // Get the minimum amount of comparisons for this number
  9. const minimum = Math.floor(val)
  10. // Get the maximum amount of comparisons for this number
  11. const maximum = Math.ceil(val)
  12. // Return the sum of the minimum and the rest (from recursive call), and the sum of the maximum and the rest (from recursive call)
  13. return [
  14. minimum + rest[0],
  15. maximum + rest[1]
  16. ]
  17. }

现在,我们的最小值和最大值有不同值的原因是因为一个是向下舍入,而另一个是向上舍入。这意味着某个数字在移动到下一个之前可能有xx + 1的比较量(除非它是2的平方积,在这种情况下,log2(n)是整数,因此只有x)。两个值的变化总是来自于每个数字的比较差异。这是唯一的变量,波动我们的可能性和范围。
那么,我们能做些什么来对抗它呢?简单,用现实的数字。在计算最小值和最大值时,我们使用理论值。
让我们假设我们在一个16个元素的数组上运行这段代码,所有的答案都是1(所以a > bb > c,等等)。假设我们正在比较第九个元素。如果进行计算,我们将看到log2(9) = 3.1699250014,这意味着我们对第9个元素的最小比较是3,最大是4。这很好,但如果我们在第12个元素上呢?好吧,因为我们总是选择1作为答案,所以我们知道第9个元素在进入下一个之前总共比较了3次。有了这些信息,我们可以摆脱最小/最大值,简单地用现有的值代替它们,因为我们不再需要依赖于理论,我们已经得到了答案。
要做到这一点,只需跟踪每个元素在进入下一个元素之前进行了多少次比较。如何做到这一点取决于你,但为了解释起见,我将创建一个名为getTotalComparisons(n)的虚构函数,它将返回数字nnull的总比较。现在,我们可以去掉最小值和最大值,但为了简单起见,我将简单地将val值替换为我们的总比较,因为整数向上或向下舍入将始终具有相同的数字。下面是它的样子:

  1. function calculateMinMax(v: number): [number, number] {
  2. // Return [0, 0] since log2(1) = 0
  3. if (v <= 1) return [0, 0]
  4. // Get the total comparisons of the current number, if any
  5. const totalComparisons = this.getTotalComparisons(v)
  6. // If `totalComparison` is not null, set `val` to `totalComparison`, else set `val` to log2 of the current number
  7. const val = (totalComparisons) ? totalComparisons : Math.log2(v)
  8. // Recursive call (can be ignored for now)
  9. const rest = this.calculateMinMax(v - 1)
  10. // Get the minimum amount of comparisons for this number
  11. const minimum = Math.floor(val)
  12. // Get the maximum amount of comparisons for this number
  13. const maximum = Math.ceil(val)
  14. // Return the sum of the minimum and the rest (from recursive call), and the sum of the maximum and the rest (from recursive call)
  15. return [
  16. minimum + rest[0],
  17. maximum + rest[1]
  18. ]
  19. }

就这样这将返回基于当前步骤的最小和最大比较量。您可以在每个答案之后(或之前)运行此函数,以了解可能还剩多少个问题。

解决方案

下面是修改后的代码,修改了calculateMinMax类以允许每步结果:

  1. class PrefList {
  2. size: number
  3. items: { item: number}[] = [{ item: 0 }]
  4. current = { item: 1, try: 0, min: 0, max: 1 }
  5. iteration: number = 0
  6. comparisonValues: {[key: number]: number} = {}
  7. constructor(n: number)
  8. constructor(n: Array<any>)
  9. constructor(n: number | Array<any>) {
  10. this.size = (typeof n == "number") ? n : n.length
  11. }
  12. addAnswer(pref: -1 | 1): void {
  13. this.iteration++
  14. if (!this.comparisonValues[this.current.item]) this.comparisonValues[this.current.item] = 0
  15. this.comparisonValues[this.current.item]++
  16. if (pref == -1) this.current.max = this.current.try
  17. else this.current.min = this.current.try + 1
  18. if (this.current.min == this.current.max) {
  19. this.items.splice(this.current.min, 0, { item: this.current.item})
  20. this.current = { item: ++this.current.item, try: 0, min: 0, max: this.items.length }
  21. }
  22. }
  23. getQuestion(): { a: number, b: number } {
  24. if (this.current.item >= this.size) return null
  25. this.current.try = Math.floor((this.current.min + this.current.max) / 2)
  26. return ({ a: this.current.item, b: this.items[this.current.try].item })
  27. }
  28. getOrder() {
  29. var index = []
  30. for (var i in this.items) {
  31. index.push(this.items[i].item)
  32. }
  33. return (index)
  34. }
  35. calculateMinMax(v: number = this.size) {
  36. if (v <= 1) return [0, 0]
  37. const comparisons = this.comparisonValues[v - 1]
  38. const val = (comparisons && this.current.item != v - 1) ? this.comparisonValues[v - 1] : Math.log2(v)
  39. const rest = this.calculateMinMax(v - 1)
  40. return [Math.floor(val) + rest[0], Math.ceil(val) + rest[1]]
  41. }
  42. }
展开查看全部

相关问题