时间戳

首页 > 解决方案 > 使用 Go 的“n”人的桥梁和火炬问题

algorithm - 使用 Go 的“n”人的桥梁和火炬问题

问题描述

问题：给定一个不同的正整数数组，表示“n”人的穿越时间。这些'n'人站在桥的一侧。Bridge 一次最多可容纳两个人。当两个人过桥时，他们必须以较慢的人的速度移动。求所有人可以过桥的最短总时间。

我无法找到如何为 'n' 人扩展它的模式。但不知何故，我设法找到了 4 个人的案例。有人可以帮我弄这个吗。我是 Golang 的新手，我被这个问题困住了。

package main

import (
    "fmt"
    "io/ioutil"
    "log"
    "os"
    "sort"

    "gopkg.in/yaml.v2"
)

type conf struct {
    Person []map[string]float32 `yaml:"person"`
}

func (c *conf) getConf() *conf {
    filename := os.Args[1]                     // Taking file input
    yamlFile, err := ioutil.ReadFile(filename) // Yaml parse
    if err != nil {
        log.Printf("yamlFile.Get err   #%v ", err)
    }
    err = yaml.Unmarshal(yamlFile, c)
    if err != nil {
        log.Fatalf("Unmarshal: %v", err)
    }
    return c
}

func main() {
    var c conf  // Object of struct conf
    c.getConf() // calling getConf function
    // Sorting the current conf map
    n := map[float32][]string{} // Map to store current conf map
    var a []float32             // Store values from conf map
    for k, v := range c.Person {
        v := float32(v)
        fmt.Println(k, v)
        n[v] = append(n[v], k)
    }
    for k := range n {
        a = append(a, k)
    }
    // Converting float32 as float64 in order to sort the values in conf map
    float32AsFloat64Values := make([]float64, len(a))
    for i, val := range a {
        float32AsFloat64Values[i] = float64(val)
    }
    sort.Float64s(float32AsFloat64Values)
    for i, val := range float32AsFloat64Values {
        a[i] = float32(val)
    }
    var time float32
    fmt.Printf("\n%v\n", a)
    for _, k := range a {
        min1 := a[0]
        min2 := a[1]
        min3 := a[2]
        for _, s := range n[k] {
            //Debug:
            fmt.Printf("%s, %g\n", s, k)
            if len(a) > 3 {
                time = (3 * min2) + min1 + a[3] //Formula for minimum time in case of 4 people
            } else if len(a) == 3 {
                time = min1 + min2 + min3
            } else {
                fmt.Println("Enter valid arguments in config.yaml")
            }
        }
    }
    fmt.Printf("Minimum time taken to cross the bridge is:\t%g\n", time)
}

游乐场： https: //play.golang.org/p/ObTVA8gk0mg

Config.yaml 是：

person:
  person_1: 2
  person_2: 1
  person_3: 5
  person_4: 8
  person_5: 9

可以将其运行为：'go run main.go config.yaml'。我的情况是这个 yaml 中可能有 4,5 或 'n' 个人。那么考虑到限制条件，他们过桥的最短时间是多少。

标签： algorithmgopattern-matchingyaml

解决方案

我认为最初的问题比所说的更有趣（是的，“桥梁和火炬”问题中必须有一个火炬！）。

例如，根据维基百科的描述，

四个人在夜里来到一条河边。有一座狭窄的桥，但一次只能容纳两个人。他们有一个手电筒，因为是晚上，过桥时必须使用手电筒。A 人 1 分钟过桥，B 人 2 分钟，C 人 5 分钟，D 人 8 分钟。当两个人一起过桥时，他们必须以较慢的人的速度移动。问题是，如果火炬只持续 15 分钟，他们能全部过桥吗？

当然，在我们的例子中，有 N 个人而不是只有四个，而且他们需要花费不同的时间才能过桥，但故事的其余部分是相同的。

这是实现：

import (
    "fmt"
    "sort"
)

func minCrossingTime(x []int) int {
    if len(x) == 1 {
        return x[0]
    }

    sort.Ints(x)

    t := 0
    a, b := x[0], x[1]
    x = x[2:]

    for len(x) >= 2 {
        n := len(x)
        c, d := x[n-2], x[n-1]
        x = x[:n-2]

        t1 := 2*b + a + d
        t2 := d + c + 2*a
        if t1 < t2 {
            t += t1
        } else {
            t += t2
        }
    }

    if len(x) == 1 {
        c := x[0]
        t += a + b + c
    } else {
        t += b
    }
    return t
}

func main() {
    x1 := []int{1, 2, 5, 8}
    fmt.Printf("x = %x, time = %d\n", x1, minCrossingTime(x1))
    x2 := []int{3, 8, 1, 6, 2, 9}
    fmt.Printf("x = %x, time = %d\n", x2, minCrossingTime(x2))
}

输出：

x = [1 2 5 8], time = 15
x = [1 2 3 6 8 9], time = 27

注意：第一个例子 [1 2 5 8] 直接来自维基百科，所以答案是肯定的，他们可以在 15 分钟内穿越

关键思想：

定义：

  • 令 X = [X1,X2,...,XN] 为交叉时间的排序数组，其中 X1 最快，XN 最慢
  • 让我们表示 {XI,XJ} 由一对人 XI 和 XJ 穿过，而 {XK} 由一个人 XK 穿过，其中 +{...} 表示在所需方向上的交叉， -{...} 在反方向

逻辑：

  1. 如果 N < 4，则问题很简单：

    • N = 1 => t = X1 (+{X1})
    • N = 2 => t = X2 (+{X1,X2})
    • N = 3 => t = X1 + X2 + X3 (+{X1,X2} -{X1} + {X1,X3})

  2. 如果 N >= 4 考虑以下问题：如何让两个最慢的人（并且只有他们）过桥并在最短的时间内将火炬带回来。有两种“好”方法可以做到这一点，时间为 t1 = X1 + 2*X2 + XN(+{X1,X2} -{X1} +{X[N-1],XN} -{X2}) 和 t2 = 2*X1 + X[N-1] + XN(+{X1,X[N- 1]} -{X1} +{X1,XN} -{X1})，所以我们从这两个中选择最好的（最小值）

  3. 现在最慢的两个已经过桥，火炬在它开始的同一侧，所以我们留下了 X' = [X1, X2, ..., X[N-2]] 的原始问题，这可以通过应用相同的逻辑并总结交叉时间来迭代解决

附加功能：

  1. 有关数学证明和更多上下文，请参见例如https://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf
  2. 用不同的编程语言编写高尔夫解决方案：https ://codegolf.stackexchange.com/questions/75615/the-bridge-and-torch-problem

推荐阅读