使整圆路径，最短路径锻炼？ [英] make the full circular path, shortest path exercise?

问题描述

我在接受采访时这个问题，我是不是能解决这个问题。

  

您有一个圆形的道路，与加油站的N多。你知道   ammount的气体，每个站都有的。你知道气体的ammount的你   需要从一个站去下一个。你的车从0开始   气体。现在的问题是：创建一个算法，要知道从哪个气   站必须开始驾驶，完成圆形路径。它确实   没有指定你必须访问所有站。你只能驱动   顺时针方向旋转。

我不得不这样做在C＃

只有code，我开始是一个GasStation实体

 类GasStation
  INT gasAtStation;
  INT gasToMoveToNextStationNeeded;
  串nameOfGasStation;


GasTation wheretoStart（名单＆LT; GasStation＆GT;名单）
{

}
 

我就是这么做的：

 静态无效的主要（字串[] args）
        {
            INT [] gasOnStation = {1，2，0,4};
            INT [] gasDrivingCostTonNextStation = {1，1,2，1};

            FindStartingPoint（gasOnStation，gasDrivingCostTonNextStation）;

        }

        静态无效FindStartingPoint（INT [] gasOnStation，INT [] gasDrivingCosts）
        {
            //假设gasOnStation.length == gasDrivingCosts.length
            INT N = gasOnStation.Length;
            INT [] gasEndValues​​ =新INT [N];
            INT gasValue = 0;
            的for（int i = 0;我n种;我++）
            {
                gasEndValues​​ [我] = gasValue;
                gasValue + = gasOnStation [I]
                gasValue  -  = gasDrivingCosts [I];
            }

            如果（gasValue℃，）
            {
                Console.WriteLine（实例没有一个解决方案）;
                到Console.ReadLine（）;
            }
            其他
            {
                //找到最小的gasEndValues​​：
                INT赠送= 0;
                INT minEndValue = gasEndValues​​ [0];
                的for（int i = 1;我n种;我++）
                {
                    如果（gasEndValues​​ [1]  - ; minEndValue）
                    {
                        MINI =我;
                        minEndValue = gasEndValues​​ [I]
                    }
                }

                Console.WriteLine（开始在车站：+ MINI）;
                到Console.ReadLine（）;
            }
        }
 

感谢

解决方案

是使用蛮力的方法解决这样一个简单的方法。即想尽posibility，扔掉那些不工作。

即。在开始依次在每个加油站（重复下面的各个始发站）。

• 有一个varible它定义了当前气平。
• 在遍历每个加油站，按顺时针顺序。
  1. 填写你的气（气增量由加油站数量）。
  2. 检查您可以移动到下一个站（气＆GT; = gasToMoveToNextStationNeeded）
     • 如果不是，这不是一个解决方案，因此移动到下一起始位置。
     • 如果是这样，减去用于气体的量，然后继续下去，直到你再次达到启动。
  3. 如果你回到起始加油站，你有一个答案。

---

修改按@ VASH的答案，作为改进决定从哪里开始的时候，打折站没有足够的气自己去下一个站，并通过启动站，以便工作气体量（降序）。

---

请注意，这是假定我们走访各个加油站。是否需要细化跳过加油站，如果你需要的最佳解决方案（问题并未指定）。

I got this question in an interview and I was not able to solve it.

You have a circular road, with N number of gas stations. You know the ammount of gas that each station has. You know the ammount of gas you need to GO from one station to the next one. Your car starts with 0 gas. The question is: Create an algorithm, to know from which gas station you must start driving to COMPLETE the circular PATH. It does not specify that you must visit all stations. You can only drive clockwise.

I had to do it in c#

The only code I started is with a GasStation entity

class GasStation
  int gasAtStation;
  int gasToMoveToNextStationNeeded;
  string nameOfGasStation;


GasTation wheretoStart(List<GasStation> list)
{

}

I did it this way:

static void Main(string[] args)
        {
            int[] gasOnStation = {1, 2, 0, 4};
            int[] gasDrivingCostTonNextStation = {1, 1,2, 1};

            FindStartingPoint(gasOnStation, gasDrivingCostTonNextStation);

        }

        static void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts)
        {
            // Assume gasOnStation.length == gasDrivingCosts.length
            int n = gasOnStation.Length;
            int[] gasEndValues = new int[n];
            int gasValue = 0;
            for (int i = 0; i < n; i++)
            {
                gasEndValues[i] = gasValue;
                gasValue += gasOnStation[i];
                gasValue -= gasDrivingCosts[i];
            }

            if (gasValue < 0)
            {
                Console.WriteLine("Instance does not have a solution");
                Console.ReadLine();
            }
            else
            {
                // Find the minimum in gasEndValues:
                int minI = 0;
                int minEndValue = gasEndValues[0];
                for (int i = 1; i < n; i++)
                {
                    if (gasEndValues[i] < minEndValue)
                    {
                        minI = i;
                        minEndValue = gasEndValues[i];
                    }
                }

                Console.WriteLine("Start at station: " + minI);
                Console.ReadLine();
            }
        }

Thanks

解决方案

One easy way of solving this is using a brute force method. i.e. try every posibility and throw out ones that don't work.

i.e. Start at each gas station in turn (repeat below for each starting station).

• Have a varible that defines current gas level.
• Loop through each gas station, in a clockwise order.
  1. Fill up your gas (increment gas by gas station amount).
  2. Check you can move to the next station (gas >= gasToMoveToNextStationNeeded)
     • If not, this isn't a solution, so move to the next starting location.
     • If so, subtract that amount of gas used, then keep going until you reach the start again.
  3. If you get back to the starting gas station you have an answer.

---

Edit As per @Vash's answer, As an improvement when deciding where to start, discount stations that don't have enough gas themselves to get to the next station and working through starting stations in order of amount of gas (descending).

---

Note, this assumes we visit all gas stations. Will need refinement for skipping gas stations if you need an optimal solution (question doesn't specify this).

这篇关于使整圆路径，最短路径锻炼？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！