# mckpath

> 路径和分堆算法js版本

Latest version **1.2.6** (published 2019-06-04) · 0 weekly downloads

## Install

```sh
npm install mckpath
pnpm add mckpath
yarn add mckpath
bun add mckpath
```

## Health

**Score 20/100 (F)** — status: abandoned.

Positive: esm support; no vulnerabilities.

Warnings: low downloads; no types.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.2.6 |
| Published | 2019-06-04 |
| First published | 2019-05-15 |
| Weekly downloads | 0 |
| TypeScript types | none |
| Module format | ESM + CommonJS |
| Dependencies | 5 |
| Unpacked size | 71.4 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| Maintainers | lornally |

## Links

- npm: https://www.npmjs.com/package/mckpath
- npm.io page: https://npm.io/package/mckpath

## Dependencies (5)

- [debug](https://npm.io/package/debug.md) latest
- [json5](https://npm.io/package/json5.md) latest
- [mcktsp](https://npm.io/package/mcktsp.md) ^0.0.8
- [stampit](https://npm.io/package/stampit.md) latest
- [mcktools](https://npm.io/package/mcktools.md) ^0.1.8

## Recent versions

- 1.2.6 (latest) — 2019-06-04
- 1.2.5 — 2019-06-03
- 1.2.4 — 2019-06-03
- 1.2.3 — 2019-06-03
- 1.2.2 — 2019-06-03
- 1.2.1 — 2019-06-03
- 1.2.0 — 2019-06-03
- 1.1.9 — 2019-06-03
- 1.1.8 — 2019-06-03
- 1.1.7 — 2019-06-03
- 1.1.6 — 2019-06-03
- 1.1.5 — 2019-06-03
- 1.1.4 — 2019-06-03
- 1.1.3 — 2019-06-03
- 1.1.2 — 2019-06-03
- … 25 more at https://npm.io/package/mckpath/versions

## README

# mckpath readme   

> 这里是path的基础结构(不含tsp)
数据结构放到了testinput.js.

###### 2019-06-03

- 10:44am 测试下stamp是否可以使用getter和setter

###### 2019-05-27

- 12:40am 半夜
  - 重写mpath部分, 加入mplan概念.
  - 并且把所有的计算都围绕时间展开, 都换算成秒.
    - 距离也是秒.
    - 权重也是秒.
  - 白天继续写一下uds-core, 看看mplan的需求.
- 11:04am
  - 写uds-core
  - 然后看线性规划.

###### 2019-05-25

- 4:20pm
  - 拨开迷雾, mpath也要遵守模式, 从自身创造自身.
- 4:32pm
  - 改造完成.

###### 2019-05-24

- 10:49am
  - path不需要知道tsp. 只要调用tsp计算最佳方案就好了.
  - tsp需要知道path的数据结构.

###### 2019-05-23

- 9:54am
  - 两种情况, 一种要做内部判断, 一种做外部判断. 依赖于path数据结构.
  - 点和订单的关系维护在点上有问题, 还是应该维护在q上, 然后在path里面保持一个对q的引用.
  - q的进度直接受外部参数的影响才可以.
  - q本身不该维护列车游标, 这个游标彻底由外部维护. q只是读取指定位置就好了.
  - 貌似这样分析, 不需要rdq了, 只要visibledot就可以了.
  - 然后, 就用… , pop, shift, push等等数组操作解决问题了.
  - visibeldot有三个数据结构
    - qs, 一个点队列数组.
    - trains, 点队列的游标数组. 如果直接处理点队列, 那么这个可以去掉.
    - keys, 可以访问的点, 如果直接操控qs, 那么这个可以省略.
- 11:39am
  - Point 不能彻底静态化, 因为他还是要记录自己的原始Q的状态. 
  - point.dad, point.no, point.s=静态引用. 
- 2:14pm
  - 最小生成树 + 线性规划可以解决时间窗口问题.
  - 最小生成树做排序用.  如果线性规划无法规划出来, 那么这个人就是不能送这一单. 
- 3:42pm
  - train测试成功.
  - 不对, 新建train的测试还没做.
- 4:13pm
  - 构思mpath.  udscore, mpath, mcktsp, 看一遍. 捋一下思路.
  - travel知道path, 拿到path的数据结构做遍历.
  - udscore知道path和travel, 安排tsp遍历path, 生成path.
  - mpath把自己作为参数传给tsp, tsp计算出最终合理的path.
- 10:38pm
  - mpoint和train验证了, 没问题了.
  - mpath要能够根据数据结构, 构造train.
- 11:35pm
  - mpath测试通过. 
  - 后面写好travel和judge就好了.

###### 2019-05-22

- 11:46am
  - visibledot不适合批量插入q, 因为每个q都有一个position的情况.
- 1:56pm
  - 遍历, 每次都保留当前局面. 顺序访问可以访问的点.
  - 然后, 在访问了某个点的情况下, 进入下一个局面. 
- 3:14pm
  - 改变思路, visibledot必须用自身的数据结构初始化, 否则可以初始化一个空的, 然后再付入点队列.
- 8:02pm
  - visibledot内部是没有状态的, 内部的q各自维护自己的状态. visibledot只要能维护好自己的每个q的可访问点就好了.



###### 2019-05-22之前

技术框架

- 全部使用stamp写法, 用sm前缀.
- 用es6 module做.



###### 

path的关系

- 所有的司机的basepath到达这个新的点的权重.



业务思路:

- 如果没有大规模重分机制, 那么算法毫无意义.
- 如果要启动大规模重分机制, 那么需要软件的导航机制, 需要这个软件是持续使用保持在前台的.



重大突破

- 用树的深度遍历长度来作为计算依据.
- driver->bus, 不再考虑订单, 他不需要知道任何订单的信息. 他只要维护自己的basepath和leftpath就好了.



整体规划:

- 有一个函数getpath, 在sa数据结构中定义了.
- 他的参数和返回值都是一个数据结构: path, 这个定义在核心数据里面.



###### -------------------------------不确定内容--------------------------------

整体思路有疑问:  todo

- 司机和路径形成矩阵关系.
- 每次选出最短路径做分配. 这个是克鲁斯卡尔思路.

一个核心思考:

- 判断是放到每个路径中. 还是放到最终权重判断的时候? 
- dijkstra是否可以让我一次把所有司机的权重算出来?

---
_Source: https://npm.io/package/mckpath · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._